package com.github.yangyishe.p200;

/**
 * 200. 岛屿数量
 * https://leetcode.cn/problems/number-of-islands/?envType=study-plan-v2&envId=top-interview-150
 * <p>
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：grid = [
 * ["1","1","1","1","0"],
 * ["1","1","0","1","0"],
 * ["1","1","0","0","0"],
 * ["0","0","0","0","0"]
 * ]
 * 输出：1
 * 示例 2：
 * <p>
 * 输入：grid = [
 * ["1","1","0","0","0"],
 * ["1","1","0","0","0"],
 * ["0","0","1","0","0"],
 * ["0","0","0","1","1"]
 * ]
 * 输出：3
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 300
 * grid[i][j] 的值为 '0' 或 '1'
 */
public class Problem200 {
    public static void main(String[] args) {
        char[][] grid = new char[][]{
                {'1', '1', '1', '0', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'0', '0', '0', '1', '0'}
        };

        Problem200 problem200 = new Problem200();
        int i = problem200.numIslands(grid);
        System.out.println(i);
    }

    /**
     * 思路:
     * 递归+回溯探索
     * 创建一个和原图大小一样的二维数组.
     * 0表示未被探索.
     * 1表示已探索且为陆地
     * 2表示已探索且为海洋
     * 从左上角开始探索. 当第一次探索到陆地时, 递归回溯法寻找剩下的陆地并全部标记
     * 已经探索过的地方不再探索. 直到最后探索完成
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        int height = grid.length;
        int width = grid[0].length;
        int[][] allMap = new int[height][width];
        int landCount = 0;
        for (int row = 0; row < height; row++) {
            for (int col = 0; col < width; col++) {
                if (allMap[row][col] > 0) {
                    continue;
                }
                if (grid[row][col] == '1') {
                    landCount++;
                }
                searchLand(grid, allMap, row, col);
            }
        }
        return landCount;
    }

    public void searchLand(char[][] grid, int[][] allMap, int row, int col) {
        if (row < 0 || row > allMap.length - 1) {
            return;
        }
        if (col < 0 || col > allMap[0].length - 1) {
            return;
        }
        if (allMap[row][col] > 0) {
            return;
        }
        // 按照从右->下->左->上的方向进行探索
        if (grid[row][col] == '0') {
            allMap[row][col] = 2;
            return;
        }
        if (grid[row][col] == '1') {
            allMap[row][col] = 1;
        }
        searchLand(grid, allMap, row, col + 1);
        searchLand(grid, allMap, row + 1, col);
        searchLand(grid, allMap, row, col - 1);
        searchLand(grid, allMap, row - 1, col);
    }

}
